package org.wiming;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * @author : wenchao.long
 * @date : Created in 2021/01/19 8:19 周二
 * @description :
 */
public class TreeNode {

    public int val;
    public TreeNode left;
    public TreeNode right;

    private TreeNode(int val) {
        this.val = val;
    }

    public static TreeNode newInstance(int val) {
        return new TreeNode(val);
    }

    public static TreeNode createTree(Deque<Integer> integers) {
        TreeNode node = null;
        if (integers == null || integers.isEmpty()) {
            return null;
        }
        Integer val = integers.remove();
        if (val != null) {
            node = newInstance(val);
            node.left = createTree(integers);
            node.right = createTree(integers);
        }
        return node;
    }

    public static TreeNode create(Deque<Integer> integers) {
        TreeNode node = null;
        if (integers == null || integers.isEmpty()) {
            return null;
        }
        Integer val = integers.remove();
        if (val != null) {
            node = newInstance(val);
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(node);
        while (!integers.isEmpty()) {
            TreeNode root = deque.poll();
            Integer leftVal = integers.poll();
            Integer rightVal = integers.poll();

            TreeNode leftNode = null;
            if (leftVal != null) {
                leftNode = newInstance(leftVal);
                deque.add(leftNode);
            }

            TreeNode rightNode = null;
            if (rightVal != null) {
                rightNode = newInstance(rightVal);
                deque.add(rightNode);
            }

            if (root != null) {
                root.left = leftNode;
                root.right = rightNode;
            }
        }
        return node;
    }

    /**
     * 前序遍历
     *
     * @return 按照前序遍历查找到的节点值组成的List
     */
    public List<Integer> preOrderList() {
        List<Integer> result = Lists.newArrayList();
        preOrderList(this, result);
        return result;
    }

    private void preOrderList(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preOrderList(root.left, result);
        preOrderList(root.right, result);
    }

    /**
     * 前序遍历 栈实现
     *
     * @return 按照前序遍历查找到的节点值组成的List
     */
    public List<Integer> preOrderListWithStack() {
        return preOrderListWithStack(this);
    }

    private List<Integer> preOrderListWithStack(TreeNode root) {
        Deque<TreeNode> stack = Lists.newLinkedList();
        List<Integer> result = Lists.newArrayList();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            // 先将左子树全部遍历完毕
            while (node != null) {
                result.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return result;
    }

    /**
     * 前序遍历 Morris 实现
     *
     * @return 按照前序遍历查找到的节点值组成的List
     */
    public List<Integer> preOrderListWithMorris() {
        return preOrderListWithMorris(this);
    }

    private List<Integer> preOrderListWithMorris(TreeNode root) {
        List<Integer> result = Lists.newArrayList();
        TreeNode p1 = root, p2;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    result.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                result.add(p1.val);
            }
            p1 = p1.right;
        }
        return result;
    }

    /**
     * 中序遍历
     *
     * @return 按照中序遍历查找到的结点值组成的List
     */
    public List<Integer> inOrderList() {
        List<Integer> result = Lists.newArrayList();
        inOrderList(this, result);
        return result;
    }

    private void inOrderList(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inOrderList(root.left, result);
        result.add(root.val);
        inOrderList(root.right, result);
    }

    /**
     * 中序遍历 stack实现
     *
     * @return 按照中序遍历查找到的节点值组成的List
     */
    public List<Integer> inOrderListWithStack() {
        return inOrderListWithStack(this);
    }

    private List<Integer> inOrderListWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = Lists.newLinkedList();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode treeNode = stack.pop();
            result.add(treeNode.val);
            root = treeNode.right;
        }
        return result;
    }

    /**
     * 中序遍历 Morris实现
     *
     * @return 按照中序遍历查找到的节点值组成的List
     */
    public List<Integer> inOrderListWithMorris() {
        return inOrderListWithMorris(this);
    }

    private List<Integer> inOrderListWithMorris(TreeNode root) {
        List<Integer> result = Lists.newArrayList();
        TreeNode pre;
        while (root != null) {
            if (root.left != null) {
                pre = root.left;
                while (pre.right != null && pre.right != root) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = root;
                    root = root.left;
                } else {
                    result.add(root.val);
                    pre.right = null;
                    root = root.right;
                }
            } else {
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }

    /**
     * 后序遍历
     *
     * @return 按照后序遍历查找到的结点值组成的List
     */
    public List<Integer> postOrderList() {
        List<Integer> result = Lists.newArrayList();
        postOrderList(this, result);
        return result;
    }

    private void postOrderList(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postOrderList(root.left, result);
        postOrderList(root.right, result);
        result.add(root.val);
    }

    /**
     * 后序遍历 栈实现
     *
     * @return 按照后序遍历查找到的节点值组成的List
     */
    public List<Integer> postOrderListWithStack() {
        return postOrderListWithStack(this);
    }

    private List<Integer> postOrderListWithStack(TreeNode root) {
        Deque<TreeNode> stack = Lists.newLinkedList();
        List<Integer> result = Lists.newArrayList();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == pre) {
                result.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return result;
    }

    public List<Integer> postOrderListWithStackRemove() {
        return postOrderListWithStackRemove(this);
    }

    private List<Integer> postOrderListWithStackRemove(TreeNode root) {
        Deque<TreeNode> stack = Lists.newLinkedList();
        LinkedList<Integer> ans = Lists.newLinkedList();
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.removeFirst();
            ans.addFirst(node.val);
            if (node.left != null) {
                stack.addFirst(node.left);
            }
            if (node.right != null) {
                stack.addFirst(node.right);
            }
        }
        return ans;
    }

    /**
     * 后序遍历 Morris实现
     *
     * @return 按照后序遍历查找到的节点值组成的List
     */
    public List<Integer> postOrderListWithMorris() {
        return postOrderListWithMorris(this);
    }

    private List<Integer> postOrderListWithMorris(TreeNode root) {
        List<Integer> res = Lists.newArrayList();
        TreeNode p1 = root, p2;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                    addPath(res, p1.left);
                }
            }
            p1 = p1.right;
        }
        addPath(res, root);
        return res;
    }

    private void addPath(List<Integer> res, TreeNode node) {
        int count = 0;
        while (node != null) {
            ++count;
            res.add(node.val);
            node = node.right;
        }
        int left = res.size() - count;
        int right = res.size() - 1;
        while (left < right) {
            int temp = res.get(left);
            res.set(left, res.get(right));
            res.set(right, temp);
            left++;
            right--;
        }
    }

    /**
     * 层次遍历
     *
     * @return 每一层的结点集合组成的List
     */
    public List<List<Integer>> levelOrderList() {
        List<List<Integer>> result = Lists.newArrayList();
        levelOrderList(this, result);
        return result;
    }

    private void levelOrderList(TreeNode root, List<List<Integer>> result) {
        Queue<TreeNode> queue = Lists.newLinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = Lists.newArrayList();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(list);
        }
    }

    /**
     * 树的深度
     *
     * @return 深度
     */
    public int depth() {
        return depth(this);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

    /**
     * 通过dfs来获取树的深度
     *
     * @return 深度
     */
    public int depthDfs() {
        return depthDfs(this);
    }

    private int depthDfs(TreeNode root) {
        Queue<TreeNode> queue = Lists.newLinkedList();
        queue.add(root);
        int result = 0;
        while (!queue.isEmpty()) {
            ++result;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return result;
    }

    public TreeNode buildTreeWithPreorderInorder(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeHelper(0, preorder.length - 1);
    }

    private int[] preorder;
    private int index;
    private final HashMap<Integer, Integer> map = new HashMap<>();

    private TreeNode buildTreeHelper(int left, int right) {
        if (left > right) {
            return null;
        }
        if (index > preorder.length) {
            return null;
        }
        int val = preorder[index++];
        TreeNode root = TreeNode.newInstance(val);
        int i = map.get(val);
        root.left = buildTreeHelper(left, i - 1);
        root.right = buildTreeHelper(i + 1, right);
        return root;
    }

}
